#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 
# Copyright (c) 2017 Baidu.com, Inc. All Rights Reserved
# 

"""
File: insertion_sort.py
Author: zhangyang(zhangyang40@baidu.com)
Date: 2017/10/30 15:44
"""


def insertionsort(list):
    for num in range(1, len(list)):
        print "num:", num

        ivalue = list[num]
        local = num

        while local > 0 and list[local - 1] > ivalue:
            print "local is:", local, "local-1 is:", local - 1, "ivalue:", ivalue
            list[local] = list[local - 1]
            local = local - 1

        list[local] = ivalue
    return list


if __name__ == '__main__':
    list2sort = [9, 3, 1, 4, 2, 7, 8, 6, 5]

    insertionsort(list2sort)
    print list2sort
